package org.example.myleet.p593;

import java.util.HashSet;
import java.util.Set;

public class Solution {
    public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
        Set<String> pointSet = new HashSet<>(4);
        pointSet.add(pointToString(p1));
        pointSet.add(pointToString(p2));
        pointSet.add(pointToString(p3));
        pointSet.add(pointToString(p4));
        if (pointSet.size() < 4) {
            return false;
        }
        int[][] points = new int[4][2];
        points[0] = p1;
        points[1] = p2;
        points[2] = p3;
        points[3] = p4;
        boolean[] visited = new boolean[points.length];
        int[][] permutation = new int[points.length][2];
        return backtrack(points, visited, 0, permutation);
    }

    private boolean backtrack(int[][] points, boolean[] visited, int i, int[][] permutation) {
        if (i == 4) {
            return isSquare(permutation[0], permutation[1], permutation[2], permutation[3]);
        }
        for (int j = 0; j < points.length; ++j) {
            if (visited[j]) {
                continue;
            }
            permutation[i] = points[j];
            visited[j] = true;
            boolean square = backtrack(points, visited, i + 1, permutation);
            if (square) {
                return true;
            }
            visited[j] = false;
        }
        return false;
    }

    private boolean isSquare(int[] topLeft, int[] topRight, int[] bottomLeft, int[] bottomRight) {
        //正方形，四个角垂直，并且对角线topLeft-bottomRight和bottomLeft-topRight垂直
        return isTopLeftPerpendicular(topLeft, topRight, bottomLeft) && isTopLeftPerpendicular(bottomRight, bottomLeft, topRight) && isTopLeftPerpendicular(bottomLeft, topLeft, bottomRight) && isTopLeftPerpendicular(topRight, bottomRight, topLeft) && isCrossPerpendicular(topLeft, topRight, bottomLeft, bottomRight);
    }

    /**
     * topLeft ➡ topRight
     * ⬇
     * bottomLeft
     */
    private boolean isTopLeftPerpendicular(int[] topLeft, int[] topRight, int[] bottomLeft) {
        int x1 = topRight[0] - topLeft[0];
        int y1 = topRight[1] - topLeft[1];
        int x2 = bottomLeft[0] - topLeft[0];
        int y2 = bottomLeft[1] - topLeft[1];
        return x1 * x2 + y1 * y2 == 0;
    }

    /**
     * topLeft ➡⬇ bottomRight
     * perpendicular to
     * bottomLeft ➡⬆ topRight
     */
    private boolean isCrossPerpendicular(int[] topLeft, int[] topRight, int[] bottomLeft, int[] bottomRight) {
        int x1 = bottomRight[0] - topLeft[0];
        int y1 = bottomRight[1] - topLeft[1];
        int x2 = bottomLeft[0] - topRight[0];
        int y2 = bottomLeft[1] - topRight[1];
        return x1 * x2 + y1 * y2 == 0;
    }

    private String pointToString(int[] p) {
        return p[0] + "_" + p[1];
    }
}
